package project.euler.honk.problem.to50;

public final class Problem46 {

	private static final int SIZE = 1000;
	private static final int[] primes = new int[SIZE];
	private static int current = 1;
	private static int currentN = 3;

	static {
		primes[0] = 2;
	}

	private static boolean isPrime(int number) {
		if (number == 1)
			return false;
		int max = (int) Math.sqrt(number);
		for (int i = 2; i <= max; i++)
			if (number % i == 0)
				return false;
		return true;
	}

	private static int getPrime(int index) {
		while (index >= current) {
			while (!isPrime(currentN))
				currentN++;
			primes[current] = currentN;
			currentN += 2;
			current++;
		}
		return primes[index];
	}

	private static boolean tryPrim(int number, int square) {
		for (int i = 0;; i++) {
			int p = getPrime(i);
			if (p > number)
				return false;
			if (square + p == number)
				return true;
		}
	}

	public static int solve() {
		int current = 0;
		for (int i = 9;; i += 2) {
			while (getPrime(current) < i)
				current++;
			if (getPrime(current) == i)
				continue;
			for (int s = 1;; s++) {
				int square = 2 * s * s;
				if (square > i)
					return i;
				if (tryPrim(i, square))
					break;
			}
		}
	}

	public static void main(String[] args) {
		long start = System.currentTimeMillis();
		long result = solve();
		long end = System.currentTimeMillis();
		System.out.println("Result: " + result + " Time: " + (end - start));
	}

}
